package com.Q04;

import com.common.TreeNode;

import java.util.ArrayList;
import java.util.Stack;

/**
 * @version v1.0.0
 * 创建时间：2022/7/4 15:01
 */
public class Q04_06 {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // 中序遍历
        ArrayList<TreeNode> iteration = iteration(root);
        for (int i=0;i<iteration.size()-1;i++){
            if (iteration.get(i).val == p.val){
                return iteration.get(i+1);
            }
        }
        return null;
    }

    private ArrayList<TreeNode> iteration(TreeNode root){
        if (root ==null) return new ArrayList<TreeNode>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        while (!stack.isEmpty()) {
            while (root.left != null) {
                stack.push(root.left);
                root = root.left;
            }
            TreeNode pop = stack.pop();
            res.add(pop);
            if (pop.right!=null){
                stack.push(pop.right);
                root =pop.right;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Integer[] integers = {6,2,8,0,4,7,9,null,null,3,5} ;
        TreeNode treeNode = TreeNode.buildTree(integers);
        new Q04_06().inorderSuccessor(treeNode,new TreeNode(2));
    }


}
